package training;

import java.util.Arrays;

/**
 * @Author liangzai
 * @Description:
 */
public class J25_7_1_Training {
    //砍竹子 I
    public int cuttingRope(int n) {
        int[] dp = new int[n+1];
        if(n <= 3) return n-1;
        /*解决大问题的时候用到小问题的解并不是这三个数
        真正的dp[1] = 0,dp[2] = 1,dp[3] = 2
        但是当n=4时，4=2+2 2*2=4 而dp[2]=1是不对的
        也就是说当n=1/2/3时，分割后反而比没分割的值要小，当大问题用到dp[j]时，说明已经分成了一个j一个i-j，这两部分又可以再分，但是再分不能比他本身没分割的要小，如果分了更小还不如不分
        所以在这里指定大问题用到的dp[1],dp[2],dp[3]是他本身*/
        dp[1] = 1;dp[2] = 2;dp[3] = 3;
        for(int i = 4; i <= n; i++) {
            for(int j = 1; j <= i/2; j++) {
                dp[i] = Math.max(dp[i],dp[i-j]*dp[j]);
            }
        }
        return dp[n];
    }


    //子数组不同元素数目的平方和 II
    int mod=(int)1e9+7;
    public int sumCounts(int[] nums) {
        int last[]=new int[100005],n=nums.length;
        long ans=0,pre=0;
        Arrays.fill(last,-1);
        SegTree st=new SegTree(0,n-1);
        build(st);
        for(int i=0;i<n;i++){
            int idx=last[nums[i]];
            pre=(pre+find(st,idx+1,i)*2+i-idx)%mod;
            ans=(ans+pre)%mod;
            update(st,idx+1,i);
            last[nums[i]]=i;
        }
        return (int)ans;
    }
    long find(SegTree st,int a,int b){
        int l=st.l,r=st.r;
        if(l==a&&r==b){return st.sum;}
        int mid=(l+r)>>1;
        clear(st);
        if(b<=mid){return find(st.left,a,b);}
        else if(a>mid){return find(st.right,a,b);}
        return (find(st.left,a,mid)+find(st.right,mid+1,b))%mod;
    }
    void update(SegTree st,int a,int b){
        int l=st.l,r=st.r;
        if(l==a&&r==b){
            st.inc++;
            st.sum=(st.sum+r-l+1)%mod;
        }
        else{
            clear(st);
            int mid=(l+r)>>1;
            if(b<=mid){update(st.left,a,b);}
            else if(a>mid){update(st.right,a,b);}
            else{
                update(st.left,a,mid);
                update(st.right,mid+1,b);
            }
            st.sum=st.left.sum+st.right.sum;
        }
    }
    void clear(SegTree st){
        int l=st.l,r=st.r;
        if(l<r&&st.inc!=0){
            int mid=(l+r)>>1;
            st.left.inc+=st.inc;
            st.right.inc+=st.inc;
            st.left.sum=(st.left.sum+(mid-l+1)*st.inc)%mod;
            st.right.sum=(st.right.sum+(r-mid)*st.inc)%mod;
            st.inc=0;
            st.sum=st.left.sum+st.right.sum;
        }
    }
    void build(SegTree st){
        int l=st.l,r=st.r;
        if(l<r){
            int mid=(l+r)>>1;
            st.left=new SegTree(l,mid);
            st.right=new SegTree(mid+1,r);
            build(st.left);
            build(st.right);
        }
    }
}
class SegTree{
    int l,r;
    long sum,inc;
    SegTree left,right;
    public SegTree(int l,int r){
        this.l=l;
        this.r=r;
        sum=0;
    }
}
